# nums=[1,5,11,5]
# nums=[1, 2, 3, 5]
nums=[100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,99,97]
#先用一种思路求解
def dfs(num,index,sumCur,target,res):
    #出口条件
    if sumCur>=target:
        if sumCur==target:
            #找到了一个结果
            res.append(True)
        return None
    for i in range(index,len(num)):
        dfs(num,i+1,sumCur+nums[i],target,res)
def canPartition(num):
    #记录整个数组的和
    sumValue=0
    for i in num:
        sumValue+=i
    target=sumValue/2
    res=[]
    dfs(num,0,0,target,res)
    if len(res)==0:
        return False
    else:
        return True

def canPartition1(nums):
    numsLenght=len(nums)
    sum=0
    for i in nums:
        sum+=i
    if (sum&1)==1:
        #对2求余
        return False  #证明和不是一个偶数，不可分割为两个子集
    target=int(sum/2)
    dp=[[False for _ in range(target+1)] for _ in range(numsLenght)]
    #先填表格第0行，第一个数只能让容积为它自己的、
    dp[0][0]=True
    dp[0][nums[0]]=True
    #
    for i in range(1,numsLenght):
        for j in range(target+1):

            #如果前面可达，那么现在也可达
            dp[i][j]=True
            if(nums[i]==j):
                dp[i][j]=True
            if nums[i]<j:
                #当前的容量可以容纳下当前的元素
                dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]]

    return dp[numsLenght-1][target]

print(canPartition1(nums))



